1. Field of the Invention
Apparatuses and systems consistent with the present invention relate generally to radio frequency identification (RFID), and more particularly, to resolution of collisions between identifiers that occurs when a RFID reader receives identifiers from a plurality of RFID tags.
2. Description of the Related Art
RFID is used to identify various devices including portable terminals and various products. The RFID technology is being developed in response to the changes in production methods, the changes in consumption patterns, and cultural and technological developments, as an alternative to bar codes and magnetic cards. The RFID card is one of contactless cards. In most cases, the contactless cards refer to the RFID cards.
An RFID, unlike the contact card, does not require a user to insert a tag into a RFID reader, is robust to friction and damage, and is insensitive to contamination or environment owing to the absence of mechanical contacts. An RFID reader constantly emits radio waves. When entering a transmission range of the RFID reader, a tag transmits its own identifier (ID) and stored data. The RFID reader forwards the received data from the tag to a server, and the server compares the received data with a pre-stored database to provide intended services. At this time, the frequency of the signal used ranges from 10 kHz to 300 GHz. Primarily, the low frequency of 134.2 kHz is used. Hereafter, the main features of the RFID are described.
First, the RFID can rapidly identify multiple tags at the same time, and thus saves the time taken for identification. In this respect, the RFID is taking the place of bar codes or magnetic tags in logistics. Secondly, the RFID, which has a wide read-range, offers high applicability according to the specification of systems or environmental conditions. For instance, the RFID tag is used in a parking control system, in place of the existing contact smart cards. Thirdly, the RFID features excellent environmental resistance and long life duration. The user needs not to insert the card into the RFID reader, and the absence of mechanical contacts for the RFID tag reduces the error rate to a minimum under adverse conditions and tag damages due to severe contact, dust, humidity, temperature, snow, rain, and so forth. Thus, the RFID tag is widely used in systems deployed outdoors. Fourthly, the RFID features the penetration through non-metallic materials. Lastly, the identification of mobile objects with high speed is allowed. It takes only 0.01 to 0.1 seconds for the RFID reader to identify tags. With this feature, the RFID system can be deployed and applied to automatic fare collection systems on highways or in tunnels.
FIG. 1 illustrates a communication system constructed with a RFID reader 100 and a plurality of tags including TAG 1, TAG 2, TAG 3, TAG 4, TAG 5 and TAG 6. As explained above, the RFID reader 100 receives and transmits data to and from TAGs 1-6. It is assumed that the plurality of TAGs 1-6 is placed within the read-range of the RFID reader 100. When the plurality of TAGs 1-6 transfers, or transmits, their data or IDs at the same time, the RFID reader 100 receives corrupted data or IDs. In other words, the RFID reader 100 cannot accurately identify the received data or IDs. To prevent this, a binary search tree algorithm has been suggested, to be described with reference to FIG. 1.
Table 1 shows IDs assigned to TAGs 1-6 as shown in FIG. 1.
TABLE 1TagsAssigned IDsTag 10000 1111Tag 20011 0011Tag 30101 0101Tag 41111 0000Tag 51100 1100Tag 61010 1010
The RFID reader 100 requests the TAGs 1-6 to transfer their assigned IDs so as to identify the tags placed in the read-range. Hereafter, a message transmitted from the RFID reader 100 is referred to as an ID request message. The RFID reader 100 transmits over its read-range an ID request message containing an ID of ‘1111 1111’ at a first time point.
The TAGs 1-6, upon receiving the ID request message, compare the ID contained in the received ID request message with their assigned IDs. When their assigned IDs are smaller than or equal to the ID contained in the ID request message according to a result of the comparison, the TAGs 1-6 transfer their IDs to the RFID reader 100.
In detail, the TAGs 1-6 transfer their assigned IDs to the RFID reader 100 since their IDs are smaller than the ID contained in the ID request message. Hereafter, the message transmitted to the tag to the RFID reader 100 is referred to as an ID response message. However, the RFID reader 100 receives the colliding (corrupted) IDs from the TAGs 1-6. Typically, as the TAGs 1-6, which have received the ID request message, transmit their ID response messages at the same time, the RFID reader 100 receives the corrupted ID ‘XXXX XXXX’.
The RFID reader 100 transmits at a second time point over its read-range another ID request message containing a reset ID in which a first corrupted bit value is reset to ‘0’ and other bit values are reset to ‘1’ based on a high-order bit of the corrupted ID. Hereafter, the lowest-order bit is referred to as a first bit and the highest-order bit is referred to as an eighth bit to facilitate the understanding of the present invention. Since the first corrupted bit, i.e., the highest-order corrupted bit, is the eighth bit, the ID contained in the ID request message is reset to ‘0111 1111’.
The TAGs 1-6, upon receiving the ID request message, compare the ID contained in the received ID request message with their assigned IDs. Only the TAGs 1-3 transfer their ID response messages according to the result of the comparison. However, the RFID reader 100 receives the corrupted ID, that is, ‘0XXX XXX1’. At a third time point, the RFID reader 100 transmits over its read-range yet another ID request message containing a reset ID in which the first corrupted bit value is reset to ‘0’ and the other bit values are reset to ‘1’ based on the highest-order of the corrupted bit of the corrupted ID. Specifically, since the seventh bit is the first corrupted bit, the ID contained in the ID request message is ‘0011 1111’.
Upon receiving the ID request message, the TAGs 1-6 compare the ID in the received ID request message with their assigned IDs. According to the result of the comparison, only the TAQs 1-2 transfer their ID response messages. Yet, the RFID reader 100 receives the corrupted ID, that is, ‘00XX XX11’. The RFID reader 100, at a fourth time point, transmits over its read-range still another ID request message containing a reset ID in which the first corrupted bit value is reset to ‘0’ and the other bit values are reset to ‘1’ based on the highest-order of the corrupted bit of the corrupted ID. Specifically, since the sixth bit is the first corrupted bit, the ID contained in the ID request message is ‘0001 1111’.
Upon receiving the ID request message, the TAGs 1-6 compare the ID in the received ID request message with their assigned IDs. According to the result of the comparisons, only the TAG 1 transfers the ID response message.
As such, the RFID reader 100 identifies the TAG 1 and performs operations to identify the TAGs 2-6. That is, the RFID reader 100 identifies only one tag at the fourth time point. At this time, the RFID reader 100 requests the TAG 1 not to send the ID response message. Upon the receiving the request, the first tag 110 does not send the ID response message even when the ID request message arrives.
By repeating the above procedure, the RFID reader 100 can recognize the IDs of the remaining tags in the sequence of TAG 2, TAG 3, TAG 6, TAG 5 and TAG 4. However, the conventional binary search tree algorithm degrades the efficiency because the collision probability increases as the number of the tags increases and the length of the ID assigned to the tag is lengthened. That is, the conventional binary search tree algorithm increases the number of transmissions of the ID request message as the number of the tags increases and the length of the ID assigned to the tags is lengthened.